package java_0220.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 使用层序遍历来看是否是对称的树
 */
public class Num101_SymmetricTreeNonRecursion {
    public boolean isSymmetric(TreeNode root) {
       Queue<TreeNode> queue=new LinkedList<>();
       //根节点不用看，直接把左右孩子的根节点入队
       queue.offer(root.left);
       queue.offer(root.right);
       while(!queue.isEmpty()){
           //一次取出两个节点，这两个节点就是两棵子树的根节点
           TreeNode t1=queue.poll();//节点出队
           TreeNode t2= queue.poll();
           if(t1==null&&t2==null){
               //左右两棵树都是空树
               //继续后面的判断
               continue;
           }
           if(t1==null||t2==null){
               //左右两棵树都是空树
               return false;
           }
           if(t1.val!=t2.val){
               return false;
           }
           //左右都不为空且根节点的节点值相同
           //继续判断t1.left和t2.right,t1.right和t2.left
           //先入队一组元素
           queue.offer(t1.left);
           queue.offer(t2.right);
           //再入队另一组元素
           queue.offer(t1.right);
           queue.offer(t2.left);
       }
       //循环执行完毕，说明对称
       return true;
    }
}
